'''
https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/description/
'''
from collections import defaultdict
from typing import List


class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        # 建图
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # f函数：填充dfn编号，和统计子树大小以dfn编号为下标，和统计子树异或和以dfn编号为下标
        dfn = [-1] * n
        sizes = [0] * n
        xor_sums = [0] * n

        def f(u, id):
            dfn[u], sizes[id], xor_sums[id] = id, 1, nums[u]
            for v in graph[u]:
                if dfn[v] != -1: continue
                f(v, id + sizes[id])
                sizes[id] += sizes[dfn[v]]
                xor_sums[id] ^= xor_sums[dfn[v]]
        root = 1        # 任意节点都可以是根
        f(root, 0)

        # for dfnid in range(n):
        #     print(f'dfnid: {dfnid}, size: {sizes[dfnid]}, xor_sum: {xor_sums[dfnid]}')
        res = float('inf')
        # 枚举删除两个点
        for a in range(1, n):
            for b in range(a + 1, n):
                # 1) 这两个节点是两个不同的子树
                # 2) 这两个节点是在一个子树上边， 由于是先序编号，所以看大编号是否是小编号的子树区间内
                # print(a, b)
                board_left, board_right = a, a + sizes[a] - 1
                if board_left <= b <= board_right:
                    # b是a的子树
                    x = xor_sums[0] ^ xor_sums[a]
                    y = xor_sums[a] ^ xor_sums[b]
                    z = xor_sums[b]
                else:
                    # a,b在两个不同的树上
                    x = xor_sums[0] ^ xor_sums[a] ^ xor_sums[b]
                    y = xor_sums[a]
                    z = xor_sums[b]
                res = min(res, max(x, y, z) - min(x, y, z))
        return res


# nums = [1,5,5,4,11]
# edges = [[0,1],[1,2],[1,3],[3,4]]
nums = [15, 20, 18, 16, 30, 5, 26, 3, 21, 29]
edges = [[5, 8], [3, 5], [5, 7], [5, 4], [4, 6], [5, 2], [3, 0], [1, 0], [7, 9]]
print(Solution().minimumScore(nums, edges))
